Enumerating five families of pattern-avoiding inversion sequences; and introducing the powered Catalan numbers

Abstract

The first problem addressed by this article is the enumeration of some families of pattern-avoiding inversion sequences. We solve some enumerative conjectures left open by the foundational work on the topics by Corteel et al., some of these being also solved independently by Lin, and Kim and Lin. The strength of our approach is its robustness: we enumerate four families F1⊂F2⊂F3⊂F4 of pattern-avoiding inversion sequences ordered by inclusion using the same approach. More precisely, we provide a generating tree (with associated succession rule) for each family Fi which generalizes the one for the family Fi−1. The second topic of the paper is the enumeration of a fifth family F5 of pattern-avo..